Approximating Soft-Capacitated Facility Location Problem With Uncertainty

摘要

We first show that a better analysis of the algorithm for The Two-SageStochastic Facility Location Problem from Srinivasan \cite{sri07} and thealgorithm for The Robust Fault Tolerant Facility Location Problem from Byrka etal \cite{bgs10} can render improved approximation factors of 2.206 and \alpha+4where \alpha is the maximum number an adversary can close, respectively, andwhich are the best ratios so far. We then present new models for the soft-capacitated facility location problemwith uncertainty and design constant factor approximation algorithms to solvethem. We devise the stochastic and robust approaches to handle the uncertaintyincorporated into the original model. Explicitly, in this paper we propose twonew problem, named The 2-Stage Soft-Capacitated Facility Location Problem andThe Robust Soft-Capacitated Facility Location Problem respectively, and presentconstant factor approximation algorithms for them both. Our method usesreductions between facility location problems and linear-cost models, therandomized thresholding technique of Srinivasan \cite{sri07} and the filteringand clustering technique of Byrka et al \cite{bgs10}.